package com.al.study.record.sort;

/**
 * Created by yuxi on 2017/8/31.
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};

        int[] insertSort = insertSort(arr);
        for (int i : insertSort) {
            System.out.print(i + "  ");
        }
        System.out.println();
        int[] insertSortByChange = insertSortByChange(arr);
        for (int i : insertSortByChange) {
            System.out.print(i + "  ");
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        if (arr.length == 0) return null;
        if (arr.length == 1) return arr;
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int j;
            //这个是我的实现思路：主要是用第i个和前面i-1个比较发现比自己大的就把该元素向右移动一个位置，
            // 直到没有比自己大就跳出，然后把自己放入当前位置+1里
            int temp = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = temp;


        }
        return arr;
    }

    /**
     * 通过交换的方式 推荐使用
     *
     * @param arr
     * @return
     */
    private static int[] insertSortByChange(int[] arr) {
        if (arr.length == 0) return null;
        if (arr.length == 1) return arr;
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int j;
            // 算法关键：第i个和前面i-1个比较，发现比自己大就交换，
            // i-1和i-2比较发现比自己大就交换.........否则就退出
            for (j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }

            }

        }
        return arr;
    }
}
